<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>1012. 至少有 1 位重复的数字</title>
  </head>
  <body>
    <script>
      //     给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。

      //

      // 示例 1：

      // 输入：n = 20
      // 输出：1
      // 解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
      // 示例 2：

      // 输入：n = 100
      // 输出：10
      // 解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
      // 示例 3：

      // 输入：n = 1000
      // 输出：262
      //

      // 提示：

      // 1 <= n <= 109

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/numbers-with-repeated-digits
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

      /**
       * @param {number} n
       * @return {number}
       */
      let numDupDigitsAtMostN = function (n) {
        const factorial = (n1) => {
          let res = 1
          for (let i = 2; i <= n1; i++) {
            res *= i
          }
          return res
        }
        let len = n.toString().length
        let count = 0

        // length < len
        for (let i = 1; i < len; i++) {
          count += (9 * factorial(9)) / factorial(9 - i + 1)
        }
        // length == len

        let num = n
        let used = new Set()
        for (let i = len - 1; i >= 0; i--) {
          let cur_dig = Math.floor(num / Math.pow(10, i))
          for (let j = i === len - 1 ? 1 : 0; j < cur_dig; j++) {
            if (!used.has(j)) {
              count += factorial(10 - len + i) / factorial(10 - len)
            }
          }
          if (used.has(cur_dig)) {
            break
          }
          used.add(cur_dig)
          num -= cur_dig * Math.pow(10, i)
        }
        let self_dup = false // if the number itself has duplicate digits
        used = new Set()
        for (let i = 0; i < len; i++) {
          let cur_dig = Math.floor(n / Math.pow(10, i)) % 10
          if (used.has(cur_dig)) {
            self_dup = true
            break
          }
          used.add(cur_dig)
        }
        if (!self_dup) {
          count++
        }
        return n - count
      }
    </script>
  </body>
</html>
